package com.leetcode.sorts.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: WuPeng
 * @Date: 2021/6/7 7:30 下午
 */
public class CountNodes_222 {

    public static int countNodes(TreeNode node){
        if (node == null) return 0;
        int left_sum = countNodes(node.left);
        int right_sum = countNodes(node.right);
        return left_sum + right_sum +1;
    }

    public static int countNodes2(TreeNode node){
        if (node == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        int sum = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            sum += queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node_tmp = queue.poll();
                if (node_tmp.left != null)
                    queue.offer(node_tmp.left);
                if (node_tmp.right != null)
                    queue.offer(node_tmp.right);
            }
        }
        return sum;
    }

}
